#include "Clever.h"
//#include "../Extern.h"

#include <vector>
#include <string>
#include <sstream>

#ifdef FRAMEWORKMEMORYTRACKER
#  include "../MemoryTracker.h"
#  define new new (__FILE__, __LINE__)
#endif

using namespace std;
using namespace CLEVER;
using namespace CLEVER::Datasets;
using namespace CLEVER::RegionDiscovery;

Clever::Clever(NumericDataset * _att_dataset,
	int _att,
	Fitness::Additive::AdditiveFitnessFunction<double> * _fit,
	DistanceFunctions::ProximitySearch<double> * _search,
	DistanceFunctions::DistanceFunction<double> * distfunc,
	Neighbourhood * neighbourhood_def, int p, int q, int useDistanceMatrix, int init_k, int isLoopPara, double rMaxRuntime, int rMaxRplcmnt, int rIncUpdate)
	: _att_dataset(_att_dataset), _att(_att), _fit(_fit), _search(_search), distfunc(distfunc), neighbourhood_def(neighbourhood_def),
	p(p), q(q), useDistanceMatrix(useDistanceMatrix), IsLoopPara(isLoopPara), _MaxRunTimeAllowed(rMaxRuntime),
	_MaxSolutionReplacementAllowed(rMaxRplcmnt), _increUpdate(rIncUpdate)
{
	useDoubleArrayDataset = 0;
	string metAtt = _att_dataset->GetMetaAttribute(_att).Keys[0];
	if (init_k > 0)
		k = init_k;
	else
		k = _att_dataset->GetMetaAttribute(_att).Keys.size();

	if (IsLoopPara != 1) {
		g_column_dataset.resize(omp_get_max_threads());
		for (int i = 0; i < omp_get_max_threads(); i++) {
			g_column_dataset[i].resize(_att_dataset->MetaData.GetDataColumn(_att).size());
		}
	}

}


Clever::Clever(DoubleArrayDataset * _att_dataset,
	int _att,
	Fitness::Additive::AdditiveFitnessFunction<double> * _fit,
	DistanceFunctions::ProximitySearch<double> * _search,
	DistanceFunctions::DistanceFunction<double> * distfunc,
	Neighbourhood * neighbourhood_def,
	int p, int q, int useDistanceMatrix, int init_k, int isLoopPara, double rMaxRuntime, int rMaxRplcmnt, int rIncUpdate)
	: _att_datasetDouble(_att_dataset), _att(_att), _fit(_fit), _search(_search), distfunc(distfunc), neighbourhood_def(neighbourhood_def),
	p(p), q(q), useDistanceMatrix(useDistanceMatrix), IsLoopPara(isLoopPara), _MaxRunTimeAllowed(rMaxRuntime),
	_MaxSolutionReplacementAllowed(rMaxRplcmnt), _increUpdate(rIncUpdate)
{
	useDoubleArrayDataset = 1;
	string metAtt = _att_dataset->GetMetaAttribute(_att).Keys[0];
	if (init_k > 0)
		k = init_k;
	else
		k = _att_datasetDouble->GetMetaAttribute(_att).Keys.size();

	if (IsLoopPara != 1) {
		for (int i = 0; i < omp_get_max_threads(); i++) {
			CLEVER::Datasets::DoubleArrayDataset * doubleArrayDatasetPt = new DoubleArrayDataset(*_att_datasetDouble);
			g_column_datasetDoubleArray.push_back(doubleArrayDatasetPt);
		}
	}

	//Deep copy test
	//		std::cout<<"pts0:"<<g_column_datasetDoubleArray[0]->GetMeta(0,1)<<endl;
	//		std::cout<<"pts1:"<<g_column_datasetDoubleArray[1]->GetMeta(0,1)<<endl;
	//		g_column_datasetDoubleArray[0]->SetMeta(0,1,100);
	//		std::cout<<"after pts0:"<<g_column_datasetDoubleArray[0]->GetMeta(0,1)<<endl;
	//		std::cout<<"after pts1:"<<g_column_datasetDoubleArray[1]->GetMeta(0,1)<<endl;
	//std::cout<<"g_column_datasetDoubleArray["<<i<<"] address = "<<&doubleArrayDatasetPt<<std::endl;

}


Clever::~Clever()
{
	/*
	   if(!vlocal_dataset.empty()){
	    for(int i = 0; i< vlocal_dataset.size();i++){
	        delete vlocal_dataset[i];
	    }
	   }*/


}


void Clever::Run(CStopWatch * rC, RunInfo * info)
{   //PROFILE_FUNC
	RandomizedSPAMAlgorithm(rC, info);
}


void Clever::RandomizedSPAMAlgorithm(CStopWatch * rC, RunInfo * rinfo)
{   //PROFILE_FUNC
	//omp_set_num_threads(2);
	vector<int> cur_reps = GenerateInitialReps();
	unsigned tDatasetSize = 0;

	if (useDoubleArrayDataset == 0)
		tDatasetSize = _att_dataset->Size();
	else
		tDatasetSize = _att_datasetDouble->Size();
	//omp_set_num_threads(1);
	cout << "Number of Thread: " << omp_get_max_threads() << ", Number of Cores:" << omp_get_num_procs() << endl;

	cout << "Initial reps: ";
	if (useDoubleArrayDataset == 0)
		for (unsigned int i = 0; i < cur_reps.size(); i++) {
			cout << cur_reps[i] << ":" << _att_dataset->GetMeta(i, 1) << ' ';
		}
	else
		for (unsigned int i = 0; i < cur_reps.size(); i++) {
			cout << cur_reps[i] << ":" << _att_datasetDouble->GetMeta(i, 1) << ' ';
		}
	cout << endl;

	vector<int> cur_nonreps = GetNonReps(cur_reps, tDatasetSize);

	NumericDataset * cur_repset = CreateRepDataset(cur_reps);
	FindRegions(cur_repset, cur_reps);
	delete cur_repset;
	cur_repset = CreateRepDataset(cur_reps);


	double cur_fit;

	if (useDoubleArrayDataset == 0)
		cur_fit = FindFitness(_fit, _att_dataset, cur_repset);
	else
		cur_fit = FindFitness(_fit, _att_datasetDouble, cur_repset);


	int count = 0;
	bool resampled[2] = { false, false };
	int resampling_count[2] = { 0, 0 };

	while (true) {
		vector< vector<int> > neighbours = neighbourhood_def->FindNeighbours(cur_reps, cur_nonreps, p);

		vector<int> best_n;
		if (IsLoopPara == 1)
			best_n = FindBestNeighbour(neighbours, cur_fit, 1, rinfo);
		else
			best_n = FindBestNeighbour(neighbours, cur_fit, rinfo);
		if (best_n.size()) {
			if (resampled[0] && !resampled[1]) {
				int tsmpl = p / 2;
				p = (tsmpl > 1) ? tsmpl : 1;
				resampled[0] = false;
			}
			if (resampled[0] && resampled[1]) {
				if (q - 2 > 0) {
					p = p / (q - 2);
				}
				resampled[0] = resampled[1] = false;
			}
			count++;
			cur_reps = best_n;
			if (useDoubleArrayDataset == 0)
				cur_nonreps = GetNonReps(cur_reps, _att_dataset->Size());
			else
				cur_nonreps = GetNonReps(cur_reps, _att_datasetDouble->Size());

			delete cur_repset;
			cur_repset = CreateRepDataset(cur_reps);
			FindRegions(cur_repset, cur_reps);
			delete cur_repset;
			cur_repset = CreateRepDataset(cur_reps);

			if (useDoubleArrayDataset == 0)
				cur_fit = FindFitness(_fit, _att_dataset, cur_repset);
			else
				cur_fit = FindFitness(_fit, _att_datasetDouble, cur_repset);
			rC->Stop();
			double timePassed = rC->GetDuration();
			cout << "Replacement with best k = " << best_n.size() << endl << "Number of replacements = " << count << endl;
			cout << "Fitness " << cur_fit << endl << "I have run:" << timePassed << " secs" << endl << endl;
			if (_MaxRunTimeAllowed > 0 && timePassed >= _MaxRunTimeAllowed) {
				cout << "Reach the Maximum Allowed Runtime, I have to stop here" << endl << endl;
				break;
			}
			if (_MaxSolutionReplacementAllowed > 0 && count >= _MaxSolutionReplacementAllowed) {
				cout << "Reach the Maximum Allowed Iterations, I have to stop here" << endl << endl;
				break;
			}

		} else if (!resampled[0]) {
			resampling_count[0]++;
			p *= 2;
			resampled[0] = true;
			cout << "Resampling once with p = " << p << ", attempt " << resampling_count[0] << endl;
		} else if (!resampled[1] && resampled[0]) {
			resampling_count[1]++;
			int tsmpl = (p / 2) * (q - 2);
			p = (tsmpl > 1) ? tsmpl : 1;
			resampled[1] = true;
			cout << "Resampling twice with p = " << p << ", attempt " << resampling_count[1] << endl;
		} else   {
			break;
		}
	}
	
	cout << "k = " << cur_reps.size() << endl;
	cout << "Fitness " << cur_fit << endl;
	cout << "Replacements: " << count << endl;
	cout << "Resampling Count (p = 2 * p): " << resampling_count[0] << endl;
	cout << "Resampling Count (p = p * (q - 2)): " << resampling_count[1] << endl;

	delete cur_repset;

	if (rinfo != 0) {
		rinfo->k = cur_reps.size();
		rinfo->fitness = cur_fit;
		rinfo->replacements = count;
	}

	FinalReps = CreateRepDataset(cur_reps);
	FindRegions(FinalReps, cur_reps);
	delete FinalReps;
	FinalReps = CreateRepDataset(cur_reps);
	FinalIndices = vector<int>(cur_reps);
	if (useDoubleArrayDataset == 0)
		FinalFitness = FindFitness(_fit, _att_dataset, FinalReps);
	else
		FinalFitness = FindFitness(_fit, _att_datasetDouble, FinalReps);
}


///  Loop Parallel
std::vector<int> Clever::FindBestNeighbour(std::vector< std::vector<int> > neighbours, double rFitness, int _loopParaFlag, RunInfo * rinfo)
{   //PROFILE_FUNC

	vector<int> best_n;
	double bestfit = rFitness;
	//printf("Start FindBestNeighbour1 bestfit=%f\n",bestfit);

	for (unsigned int i = 0; i < neighbours.size(); i++) {
		vector<int> & neighbour = neighbours[i];
		NumericDataset * newrepset = CreateRepDataset(neighbour);
		if (_increUpdate == 1) {
			if (i > 0) {
				vector<int> & prevneighbour = neighbours[i - 1];
				FindRegionsIterative(newrepset, neighbour, prevneighbour);
			} else   {
				FindRegions(newrepset, neighbour);
			}
		} else  {
			FindRegions(newrepset, neighbour);
		}

		delete newrepset;

		newrepset = CreateRepDataset(neighbour);
		//delete newrepset;

		if (rinfo) {
			rinfo->iterations++;
		}
		double newfit;
		if (useDoubleArrayDataset == 0)
			newfit = FindFitness(_fit, _att_dataset, newrepset);
		else
			newfit = FindFitness(_fit, _att_datasetDouble, newrepset);
		delete newrepset;
		//cout << newfit << ' ' << neighbour.size() << endl;
		//	printf("  Neighbour%d,newfit=%f\n",i,newfit);
		if (newfit > bestfit) {
			bestfit = newfit;
			best_n = neighbour;
		}
	}
	//cout << "Chose: " << best_n.size() << " ";
	//if (best_n.size())
	//{
	//	cout << "(";
	//	for (int i = 0; i < best_n.size(); i++)
	//	{
	//		cout << best_n[i];
	//		if (i < best_n.size() - 1) { cout << ", "; }
	//	}
	//	cout << ") ";
	//}
	//cout << "with fitness " << bestfit << endl;
	//printf("End FindBestNeighbour1 bestfit=%f, best_n size=%d\n",bestfit,best_n.size());
	return best_n;
}


///  Task Parallel
std::vector<int> Clever::FindBestNeighbour(std::vector< std::vector<int> > neighbours, double rFitness, RunInfo * rinfo)
{   //PROFILE_FUNC

	vector<int> best_n;
	double bestfit = rFitness;

	vector< vector<int> > local_best_n(omp_get_max_threads());
	vector<double> local_bestfit(omp_get_max_threads(), rFitness);

	int numThreads = omp_get_max_threads();
	int lastSize = neighbours.size() - (numThreads - 1) * (neighbours.size() / numThreads);
	int iSize = neighbours.size() / numThreads;
	int startTid = numThreads - (lastSize - iSize);
	//printf("Start FindBestNeighbour0 bestfit=%f\n",bestfit);
#pragma omp parallel //added by Panitee
	{
		int tid = omp_get_thread_num();
		///bool flag = false;
		//vector<int> local_best_n;
		//double local_bestfit = rFitness;
		size_t iStart;
		size_t iEnd;
		if (lastSize - 1 > iSize) {
			if (tid == startTid) {
				iStart = tid * iSize;
				iEnd = iStart + iSize + 1;
			} else if (tid > startTid) {
				iStart = tid * iSize + (tid - startTid);
				iEnd = iStart + iSize + 1;
			} else {
				iStart = tid * iSize;
				iEnd = iStart + iSize;
			}
		} else {
			iStart = tid * iSize;
			iEnd = tid == numThreads - 1 ? neighbours.size() : iStart + iSize;
		}
		//printf("Thread %d of %d,startTid %d, lastSize %d, iSize %d, iStart %d, iEnd %d\n",tid,startTid,numThreads,lastSize,iSize,iStart,iEnd);
		///	#pragma omp for
		///	for (unsigned int i = 0; i < neighbours.size(); i++)
		for (size_t i = iStart; i < iEnd; i++) {
			vector<int> & neighbour = neighbours[i];
			NumericDataset * newrepset = CreateRepDataset(neighbour);

			if (_increUpdate == 1) {
				if (i > iStart) {
					///if (flag)
					vector<int> & prevneighbour = neighbours[i - 1];
					FindRegionsIterative(newrepset, neighbour, prevneighbour, g_column_dataset[tid]);
				} else   {
					if (useDoubleArrayDataset == 0) {
						FindRegions(newrepset, neighbour, g_column_dataset[tid]);
					} else   {
						FindRegions(newrepset, neighbour, g_column_datasetDoubleArray[tid]);
					}
					///flag = true;
				}
			} else  {
				if (useDoubleArrayDataset == 0) {
					FindRegions(newrepset, neighbour, g_column_dataset[tid]);
				} else   {
					FindRegions(newrepset, neighbour, g_column_datasetDoubleArray[tid]);
				}
			}

			delete newrepset;

			newrepset = CreateRepDataset(neighbour);


			if (rinfo) {
#pragma omp atomic
				rinfo->iterations++;
			}

			double newfit = 0;
			if (useDoubleArrayDataset == 0) {
				newfit = FindFitness(_fit, g_column_dataset[tid], _att_dataset, newrepset);
			} else
				newfit = FindFitness(_fit, g_column_datasetDoubleArray[tid], newrepset);


			delete newrepset;

			//	printf("  Neighbour%d,newfit=%f\n",i,newfit);
			if (newfit > local_bestfit[tid]) {
				local_bestfit[tid] = newfit;
				local_best_n[tid] = neighbour;
			}
		}
		/*
		   #pragma omp critical
		    {
		        if(local_bestfit > bestfit){
		          printf("Thread %d,local_bestfit %f, bestfit %f\n",omp_get_thread_num(),local_bestfit,bestfit);
		              bestfit = local_bestfit;
		              best_n = local_best_n;
		        }
		    }
		 */

	}
	for (int i = 0; i < omp_get_max_threads(); i++) {
		if (local_bestfit[i] > bestfit) {
			bestfit = local_bestfit[i];
			best_n = local_best_n[i];
		}
	}

	return best_n;
}


std::vector<int> Clever::GenerateInitialReps()
{   //PROFILE_FUNC

	vector<int> reps;

	for (int i = 0; i < k; ) {
		int r;
		if (useDoubleArrayDataset == 0)
			r = rand() % _att_dataset->Size();
		else
			r = rand() % _att_datasetDouble->Size();

		bool has = false;
		for (unsigned int j = 0; j < reps.size(); j++) {
			if (reps[j] == r) {
				has = true; break;
			}
		}
		if (!has) {
			reps.push_back(r);
			i++;
		}
	}

	return reps;
}


std::vector<int> Clever::GetNonReps(std::vector<int> & rReps, int rSize)
{   //PROFILE_FUNC

	vector<int> nonreps;
	for (int i = 0; i < rSize; i++) {
		bool has = false;
		for (unsigned int j = 0; j < rReps.size(); j++) {
			if (rReps[j] == i) {
				has = true; break;
			}
		}
		if (!has) {
			nonreps.push_back(i);
		}
	}
	return nonreps;
}


NumericDataset * Clever::CreateRepDataset(vector<int> rReps)
{   //PROFILE_FUNC

	NumericDataset * repset = new NumericDataset();
	int tNumRealAtt, tNumMetaAtt;

	if (useDoubleArrayDataset == 0) {
		repset->MetaData.attributes = _att_dataset->MetaData.attributes;
		repset->RealData.attributes = _att_dataset->RealData.attributes;
		tNumRealAtt = _att_dataset->GetNumAttributes();
		tNumMetaAtt = _att_dataset->GetNumMetaAttributes();
	} else  {
		repset->MetaData.attributes = _att_datasetDouble->MetaData.attributes;
		repset->RealData.attributes = _att_datasetDouble->RealData.attributes;
		tNumRealAtt = _att_datasetDouble->GetNumAttributes();
		tNumMetaAtt = _att_datasetDouble->GetNumMetaAttributes();
	}
	int count = rReps.size();

	//std::cout<<"Count:"<<count<<std::endl;

	int iDestBase = repset->Append(count);
	for (int i = 0; i < count; i++) {
		int iDest = iDestBase + i;
		for (int j = 0; j < tNumRealAtt; j++) {
			if (useDoubleArrayDataset == 0)
				repset->SetValue(iDest, j, _att_dataset->GetValue(rReps[i], j));
			else
				repset->SetValue(iDest, j, _att_datasetDouble->GetValue(rReps[i], j));
		}
		for (int j = 0; j < tNumMetaAtt; j++) {
			if (useDoubleArrayDataset == 0)
				repset->SetMeta(iDest, j, _att_dataset->GetMeta(rReps[i], j));
			else
				repset->SetMeta(iDest, j, _att_datasetDouble->GetMeta(rReps[i], j));
		}
	}

	return repset;
}


NumericDataset * Clever::FindRegionsIterative(NumericDataset * rep_set, std::vector<int> & cur, std::vector<int> & prev)
{
	if (useDoubleArrayDataset == 0)
		UpdateNumOfRegions(_att_dataset->MetaData.attributes[_att], rep_set->Size());
	else
		UpdateNumOfRegions(_att_datasetDouble->MetaData.attributes[_att], rep_set->Size());

	size_t imax;
	if (useDoubleArrayDataset == 0) {
		imax = _att_dataset->MetaData.data.size();
	} else  {
		imax = _att_datasetDouble->MetaData._nExample;
	}
	//RegionDiscovery::DistanceFunctions::KDSubdiv subdiv;
	//subdiv.Populate(rep_set);
	vector<int> remap_old, remap_new;
	int remap_size = 0;
	vector<int> adds, removes;
	int cursize = cur.size();
	int prevsize = prev.size();
	adds.reserve(cursize);
	removes.reserve(cursize);
	remap_old.reserve(cursize);
	remap_new.reserve(cursize);
	for (int i = 0; i < cursize; i++) {
		bool has = false;
		for (int j = 0; j < prevsize && !has; j++) {
			if (cur[i] == prev[j]) {
				has = true;
			}
		}

		if (!has) {
			adds.push_back(i);
		}
	}

	for (int i = 0; i < cursize; i++) {
		for (int j = 0; j < prevsize; j++) {
			if (cur[i] == prev[j]) {
				remap_old.push_back(j);
				remap_new.push_back(i);
				++remap_size;
				break;
			}
		}

	}

	for (int i = 0; i < prevsize; i++) {
		bool has = false;
		for (int j = 0; j < cursize && !has; j++) {
			if (prev[i] == cur[j]) {
				has = true;
			}
		}

		if (!has) {
			removes.push_back(i);
		}
	}

	int removes_size = removes.size();
	//#ifndef FRAMEWORKPROFILER
#pragma omp parallel for schedule(dynamic)
	//#endif
	for (int i = 0; i < (int)(imax); i++) {
		int tiNN;
		if (useDoubleArrayDataset == 0)
			tiNN = (int)(_att_dataset->GetMeta(i, _att));
		else
			tiNN = (int)(_att_datasetDouble->GetMeta(i, _att));
		int orig = tiNN;

		if (prevsize == 0) {
			tiNN = -1;
		} else if (tiNN != -1) {
			for (int i = 0; i < removes_size; ++i) {
				if (tiNN == removes[i]) {
					tiNN = -1; break;
				}
			}
		}

		if (tiNN != -1) {
			int extra_index = -1;
			for (int r = 0; r < remap_size; ++r) {
				if (orig == remap_old[r]) {
					extra_index = remap_new[r]; break;
				}
			}
			if (useDoubleArrayDataset == 0)
				tiNN = _search->NearestNeighbourIndices(rep_set, _att_dataset, i, adds, extra_index);
			else
				tiNN = _search->NearestNeighbourIndices(rep_set, _att_datasetDouble, i, adds, extra_index);
		} else   {
			if (useDoubleArrayDataset == 0)
				tiNN = _search->NearestNeighbour(rep_set, _att_dataset, i);
			else
				tiNN = _search->NearestNeighbour(rep_set, _att_datasetDouble, i);
		}

		if (useDoubleArrayDataset == 0)
			_att_dataset->SetMeta(i, _att, tiNN);
		else
			_att_datasetDouble->SetMeta(i, _att, tiNN);
	}

	return useDoubleArrayDataset == 0 ? _att_dataset : _att_datasetDouble;
}


NumericDataset * Clever::FindRegions(NumericDataset * rep_set, std::vector<int> & cur)
{   //PROFILE_FUNC


	size_t imax;

	if (useDoubleArrayDataset == 0) {
		UpdateNumOfRegions(_att_dataset->MetaData.attributes[_att], rep_set->Size());
		imax = _att_dataset->MetaData.data.size();
	} else  {
		UpdateNumOfRegions(_att_datasetDouble->MetaData.attributes[_att], rep_set->Size());
		imax = _att_datasetDouble->MetaData._nExample;
	}
	//RegionDiscovery::DistanceFunctions::KDSubdiv subdiv;
	//subdiv.Populate(rep_set);

	//#ifndef FRAMEWORKPROFILER
#pragma omp parallel for
	//#endif
	for (int i = 0; i < (int)imax; i++) {
		int iNN;
		if (useDistanceMatrix == 0) { //0: not using distance matrix
			if (useDoubleArrayDataset == 0)
				iNN = _search->NearestNeighbour(rep_set, _att_dataset, i);
			else
				iNN = _search->NearestNeighbour(rep_set, _att_datasetDouble, i);
		} else
			iNN = _search->NearestNeighbourMatrix(cur, i);

		//int iNN = -1;
		//double bestdist = 0;
		//subdiv.root.GetNearestNeighbour(distfunc, false, _att_dataset, i, iNN, bestdist);

		//_search->NearestNeighbour(rep_set, _att_dataset, i);
		if (useDoubleArrayDataset == 0)
			_att_dataset->SetMeta(i, _att, iNN);
		else
			_att_datasetDouble->SetMeta(i, _att, iNN);
	}


	return _att_dataset;
}


//added by Panitee for OpenMP modification for task parallel
void Clever::FindRegions(NumericDataset * rep_set, std::vector<int> & cur, NumericDataset * data)
{
	UpdateNumOfRegions(data->MetaData.attributes[_att], rep_set->Size());
	size_t imax = data->MetaData.data.size();
	for (int i = 0; i < (int)imax; i++) {
		int iNN;
		if (useDistanceMatrix == 0) //0: not using distance matrix
			iNN = _search->NearestNeighbour(rep_set, _att_dataset, i);
		else
			iNN = _search->NearestNeighbourMatrix(cur, i);
		//int iNN = _search->NearestNeighbourMatrix(cur, i);
		data->SetMeta(i, _att, iNN);
	}
}


//added by Panitee for OpenMP modification for task parallel
void Clever::FindRegionsIterative(NumericDataset * rep_set, std::vector<int> & cur, std::vector<int> & prev, std::vector<double> & data)
{
	size_t imax = data.size();

	//RegionDiscovery::DistanceFunctions::KDSubdiv subdiv;
	//subdiv.Populate(rep_set);
	vector<int> remap_old, remap_new;
	int remap_size = 0;
	vector<int> adds, removes;
	int cursize = cur.size();
	int prevsize = prev.size();
	adds.reserve(cursize);
	removes.reserve(cursize);
	remap_old.reserve(cursize);
	remap_new.reserve(cursize);
	for (int i = 0; i < cursize; i++) {
		bool has = false;
		for (int j = 0; j < prevsize && !has; j++) {
			if (cur[i] == prev[j]) {
				has = true;
			}
		}

		if (!has) {
			adds.push_back(i);
		}
	}

	for (int i = 0; i < cursize; i++) {
		for (int j = 0; j < prevsize; j++) {
			if (cur[i] == prev[j]) {
				remap_old.push_back(j);
				remap_new.push_back(i);
				++remap_size;
				break;
			}
		}

	}

	for (int i = 0; i < prevsize; i++) {
		bool has = false;
		for (int j = 0; j < cursize && !has; j++) {
			if (prev[i] == cur[j]) {
				has = true;
			}
		}

		if (!has) {
			removes.push_back(i);
		}
	}

	int removes_size = removes.size();

	for (int i = 0; i < (int)(imax); i++) {
		int tiNN = (int)data[i];
		int orig = tiNN;

		if (prevsize == 0) {
			tiNN = -1;
		} else if (tiNN != -1) {
			for (int i = 0; i < removes_size; ++i) {
				if (tiNN == removes[i]) {
					tiNN = -1; break;
				}
			}
		}

		if (tiNN != -1) {
			int extra_index = -1;
			for (int r = 0; r < remap_size; ++r) {
				if (orig == remap_old[r]) {
					extra_index = remap_new[r]; break;
				}
			}
			tiNN = _search->NearestNeighbourIndices(rep_set, _att_dataset, i, adds, extra_index);
		} else   {
			tiNN = _search->NearestNeighbour(rep_set, _att_dataset, i);
		}

		data[i] = tiNN;
	}
}


void Clever::FindRegions(NumericDataset * rep_set, std::vector<int> & cur, std::vector<double> & data)
{
	//UpdateNumOfRegions(data->MetaData.attributes[_att], rep_set->Size());
	size_t imax = data.size();

	for (int i = 0; i < (int)imax; i++) {
		int iNN;
		if (useDistanceMatrix == 0) { //0: not using distance matrix
			iNN = _search->NearestNeighbour(rep_set, _att_dataset, i);
		} else
			iNN = _search->NearestNeighbourMatrix(cur, i);
		//int iNN = _search->NearestNeighbourMatrix(cur, i);
		data[i] = iNN;
	}
}


void Clever::FindRegions(NumericDataset * rep_set, std::vector<int> & cur, DoubleArrayDataset * data)
{
	UpdateNumOfRegions(data->MetaData.attributes[_att], rep_set->Size());
	size_t imax = data->MetaData._nExample;
	for (int i = 0; i < (int)imax; i++) {
		int iNN;
		if (useDistanceMatrix == 0) { //0: not using distance matrix
			iNN = _search->NearestNeighbour(rep_set, _att_datasetDouble, i);
		} else
			iNN = _search->NearestNeighbourMatrix(cur, i);
		//int iNN = _search->NearestNeighbourMatrix(cur, i);
		data->SetMeta(i, _att, iNN);
	}
}


void Clever::UpdateNumOfRegions(Attribute & attr, int k)
{   //PROFILE_FUNC

	int cur_k = attr.Keys.size();

	if (cur_k > k) {
		int diff = cur_k - k;
		int len = cur_k - 1;
		vector<string> keys;
		for (int i = 0; i < diff; i++) {
			keys.push_back(attr.GetKey(len--));
		}
		attr.RemoveKeys(keys);
	} else if (cur_k < k) {
		int diff = k - cur_k;
		int len = cur_k;
		vector<string> keys;
		for (int i = 0; i < diff; i++) {
			ostringstream buf;
			buf << "R" << len++;
			//char buf[256] = { 0 };
			//sprintf_s(buf, 256, "R%d", len++);
			keys.push_back(buf.str().c_str());
		}
		attr.AddKeys(keys);
	}
}


double Clever::FindFitness(Fitness::Additive::AdditiveFitnessFunction<double> * _fit, DoubleArrayDataset * data, NumericDataset * repSet)
{   //PROFILE_FUNC
	//_fit->Precompute(data);
	//float f1 = _fit->Fitness();
	_fit->Precompute(data, true);
	return _fit->Fitness(data, _att, repSet); //Modify: need to pass in centroid set
}


double Clever::FindFitness(Fitness::Additive::AdditiveFitnessFunction<double> * _fit, NumericDataset * data, NumericDataset * repSet)
{   //PROFILE_FUNC
	//_fit->Precompute(data);
	//float f1 = _fit->Fitness();
	_fit->Precompute(data, true);
	return _fit->Fitness(data, _att, repSet); //Modify: need to pass in centroid set
}

/// For task parallel
double Clever::FindFitness(Fitness::Additive::AdditiveFitnessFunction<double> * _fit, std::vector<double> & data, NumericDataset * g_data, NumericDataset * repSet)
{   //PROFILE_FUNC
	//_fit->Precompute(data);
	//float f1 = _fit->Fitness();
	_fit->Precompute(data);
	return _fit->Fitness(data, g_data, _att, repSet); //Modify: need to pass in centroid set
}


